package LeetCodeHot100TopInterview;

public class Q033_RotateArrayFind {

    //同剑指offer_q11 == > 找旋转点
    //此处 ==> 在旋转数组上进行二分查找 ==> 不含重复值版 ==> medium
    //尽力二分
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0){
            return Integer.MAX_VALUE;
        }
        int left = 0;
        int right = nums.length - 1;
        int mid = -1;
        while (left <= right){
//            mid = left + ((right - left) >> 2) ;
            mid = (left + right) / 2;
            //在左半边
            if (target == nums[mid]){
                return mid;
            }
            if (nums[mid] > nums[0]){
                if (target >= nums[0] && target < nums[mid]){
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
             }else {
                if (target <= nums[nums.length - 1] && target > nums[mid]){
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }
            }
    }
        return -1;
}

    public static void main(String[] args) {
        Q033_RotateArrayFind fun = new Q033_RotateArrayFind();
        System.out.println(fun.search(new int[]{3,1}, 1));
    }
}
